/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/parser
   @Language: C++
   @Datetime: 19-06-25 10:04
   */

class Solution {
	bool dfs(const string &start, const string &end, 
			unordered_map<char,unordered_set<string> > &gen){
		if(start.length()>end.length()) return false;
		if(start.compare(end)==0) return true;
		for(int i=0; i<start.length(); ++i){
			if(start[i]<'A' || start[i]>'Z') continue;
			for(const auto &str:gen[start[i]]){
				string newstart=start.substr(0,i)+str+start.substr(i+1);
				if(dfs(newstart,end,gen)) return true;
			}
		}
		return false;
	}
public:
	/**
	 * @param generator: Generating set of rules.
	 * @param startSymbol: Start symbol.
	 * @param symbolString: Symbol string.
	 * @return: Return true if the symbol string can be generated, otherwise return false.
	 */
	bool canBeGenerated(vector<string> &generator, char startSymbol, string &symbolString) {
		// Write  your code here.
		unordered_map<char,unordered_set<string> > gen;
		for(const auto &str:generator)
			gen[str[0]].insert(str.substr(5));
		for(const auto &str:gen[startSymbol])
			if(dfs(str,symbolString,gen)) return true;
		return false;
	}
};
